import java.util.Arrays;

public class 按公因数计算最大组件大小 {
    public static int MAXN = 20001;
    public static int MAXV = 100001;
    // 第一个出现质因子的数
    public static int[] factors = new int[MAXV];
    // 存储下标然后来连接
    public static int farther[] = new int[MAXN];
    public static int size[] = new int[MAXN];
    public static int n;
    public int largestComponentSize(int[] nums) {
        n = nums.length;
        build();
        for (int i = 0; i < n; i++) {
            int x = nums[i];
            for (int j = 2; j * j <= x; j++) {
                if (x % j == 0) {
                    if (factors[j] == -1) {
                        factors[j] = x;
                    } else {
                        // 合并下标
                        union(factors[j], i);
                    }
                    while (x % j == 0) {
                        x /= j;
                    }
                }
            }
            if (x > 1) {
                if (factors[x] == -1) {
                    factors[x] = i;
                } else {
                    union(factors[x],i);
                }
            }
        }
        return maxSize();
    }

    private static int maxSize() {
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans,size[i]);
        }
        return ans;
    }

    public static void build () {
        for (int i = 0; i < n; i++) {
            farther[i] = i;
            size[i] = 1;
        }
        Arrays.fill(factors,-1);
    }

    public static int find (int i) {
        if (farther[i] != i) {
            farther[i] = find(farther[i]);
        }
        return farther[i];
    }

    public static void union (int x,int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            farther[fx] = fy;
            size[fy] += size[fx];
        }
    }
    
}
